//
//  快速排序.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/3/3.
//

import Foundation

/// 快速排序(递归法)
/// - Parameter arr: 待排序的数组
/// - Returns: 排序后的数组
func quickSortRecursion(_ arr: [Int]) -> [Int] {
    guard arr.count > 1 else { return arr }
    var a = arr
    
    // 获取分区点
    func partition(_ arr: inout [Int], _ l: Int, _ r: Int) -> Int {
        let pivot = arr[r]
        var i = l
        for j in l..<r {
            if arr[j] < pivot {
                arr.swapAt(i, j)
                i += 1
            }
        }
        arr.swapAt(i, r)
        return i
    }
    
    // 快速排序递归函数，l,r为下标
    func sort(_ arr: inout [Int], _ l: Int, _ r: Int) {
        if l >= r { return }
        
        let p = partition(&arr, l, r)
        sort(&arr, l, p - 1)
        sort(&arr, p + 1, r)
    }
    
    sort(&a, 0, a.count - 1)
    
    return a
}

/// 快速排序(模拟栈)
/// - Parameter arr: 待排序的数组
/// - Returns: 排序后的数组
func quickSortStack(_ arr: [Int]) -> [Int] {
    guard arr.count > 1 else { return arr }
    var a = arr
    
    // 获取分区点
    func partition(_ arr: inout [Int], _ l: Int, _ r: Int) -> Int {
        let pivot = arr[r]
        var i = l
        for j in l..<r {
            if arr[j] < pivot {
                arr.swapAt(i, j)
                i += 1
            }
        }
        arr.swapAt(i, r)
        return i
    }
    
    // 快速排序递归函数，l,r为下标
    func sort(_ arr: inout [Int], _ l: Int, _ r: Int) {
        if l >= r { return }
        // 创建栈
        var stack = Stack<(Int, Int)>()
        stack.push(element: (l, r))
        while stack.count > 0 {
            let (a, b) = stack.pop()!
            if a < b {
                let p = partition(&arr, a, b)
                stack.push(element: (a, p - 1))
                stack.push(element: (p + 1, b))
            }
        }
    }
    sort(&a, 0, a.count - 1)
    
    return a
}
